The present invention relates to statistical data compression, and more particularly to binary arithmetic coding.
Data compression works by encoding data according to a certain format to reduce the amount of data that needs to be transmitted in a system. A decoder can then decode the encoded data utilizing the same format to convert the data back to their original state. Many examples of data compression exist, although developments and improvements to conventional techniques are constantly being made.
Arithmetic coding is a form of data compression that takes a plurality of symbols, processes them, and writes the codes to a file. Arithmetic coding utilizes probability estimation in order to code symbols, by assigning each symbol an interval of a range, wherein the range parameters are 0 and 1. In probability estimation, a symbol that has greater probability of appearing is assigned a greater part of the range, and a symbol that has less probability of appearing is assigned the smaller part of the range. This probability estimation will be described in more detail in the following.
For example, when coding a bin string “010”, a probability of symbol “1” is 0.4, and a probability of “0” is 0.6. Therefore, “0” is the most probable symbol (MPS) and “1” is the least probable symbol (LPS) in this example. Initially, a range is 200, and a low value is 0. When the first symbol “0” is coded, as the probability of “0” is 0.6, the range will be 0.6 of 200, or 120. Because the MPS occupies the lower part of the range, the low value will remain as 0. For the next symbol, the probability of “1” is 0.4, so the range now becomes 0.4 of 120, or 48. As the LPS occupies the upper part of the range, the new low value is 72. Finally, for the symbol “0”, the new range becomes 0.6 of 48, or 28.8, and the low value will remain the same.
Binary arithmetic coding is a form of arithmetic coding that converts all symbols into binary form before processing. The binary arithmetic coding process occurs in four stages. The first stage is the binarization stage, where each symbol is converted into a binary value (bin), thereby forming a bin stream. In the second stage, a context model (probability model) is chosen, based on previously coded bins. In the third stage, each bin is coded according to a current context model, and in the fourth stage the context model is updated according to the coded bin. In binary arithmetic coding, the range value is a 9-bit value, wherein bit 9 is the most significant bit (MSB), and shows whether the range has fallen below 256 or not.
Context Adaptive Binary Arithmetic Coding (CABAC) is a well-known form of arithmetic coding, that updates the probability each time a bin is coded, according to previously coded bins. CABAC utilizes LPS look-up tables (LUTs), containing a plurality of possible range values. A current context model and bits 7 and 8 of a current range are input to the LPS LUT and a predicted range value according to this information is output.
Please refer to FIG. 1. FIG. 1 is a diagram of a bin coding engine 100. The bin coding engine 100 comprises an LPS coding table 120, a subtracter 130, and an adder 140. Initially, a previous range and a context model are input to the LPS coding table 120, which outputs a first LPS range according to this information. The bin coding engine 100 also determines a first MPS range by subtracting the first LPS range from the previous range using the subtracter 130. Additionally, a previous low value of the previous range is input to the bin coding engine 100. If the current bin is an MPS, the low value will remain the same (please see the example in the above paragraph), so this value can be directly output. If the current bin is an LPS, however, the low value must be added to the first MPS range output from the subtracter 130. This operation is performed by the adder 140.
As can be seen from the above description, the coding operation for each bin is complicated. In the conventional art, as each bin must be coded sequentially, the throughput is limited.